package com.wc.alorithm_luogu.P4017;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;

/**
 * @Author congge
 * @Date 2023/9/28 22:01
 * @description 最大食物链计数
 * https://www.luogu.com.cn/problem/P4017
 */
public class Main {
    public static void main(String[] args) {
        Input scan = new Input();
        int n = scan.nextInt();
        int m = scan.nextInt();

        /**
         * eatOrEatEd[i][j] 表示 i 是否会被 j 吃
         */
        boolean[][] eatOrEatEd = new boolean[n + 1][n + 1];
        int[] dp = new int[n + 1];
        int i;
        int j;
        /**
         * 是不是不是食物链顶端
         */
        boolean[] isNotTop = new boolean[n + 1];
        while (m-- > 0) {
            i = scan.nextInt();
            j = scan.nextInt();
            eatOrEatEd[i][j] = true;
            isNotTop[i] = true;
        }
        Main main = new Main();

        for (int k = 1; k <= n; k++) {
            main.deepScan(eatOrEatEd, k, dp);
        }
        int ans = 0;
        for (int k = 1; k <= n; k++) {
            if (!isNotTop[k]) {
                ans += dp[k];
                ans = ans % 80112002;
            }
        }

        System.out.println(ans % 80112002);
    }

    public int deepScan(boolean[][] eatOrEatEd, int i, int[] dp) {
        if (dp[i] != 0) {
            return dp[i];
        }

        int ans = 0;

        for (int j = 1; j < eatOrEatEd.length; j++) {
            if (eatOrEatEd[j][i]) {
                ans += deepScan(eatOrEatEd, j, dp);
                ans %= 80112002;
            }
        }

        /**
         * 如果说他最后的还是0说明他是最低端的
         */
        if (ans == 0) {
            ans = 1;
        }

        dp[i] = ans % 80112002;
        return dp[i];
    }

    static class Input {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

        public int nextInt() {
            try {
                in.nextToken();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return (int) in.nval;
        }
    }
}
